import { btPrint, PrintableNode } from "hy-algokit";

export class TreeNode<T> {
  value: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
  root: TreeNode<T> | null;

  constructor(value: T, left?: TreeNode<T> | null, right?: TreeNode<T> | null, parent?: TreeNode<T> | null) {
    this.value = value;
    this.left = left || null;
    this.right = right || null;
    this.root = parent || null;
  }

  get isLeft(): boolean {
    return !!(this.root && this.root.left === this);
  }

  get isRight(): boolean {
    return !!(this.root && this.root.right === this);
  }
}

export default class SearchTree<T> implements PrintableNode {
  root: TreeNode<T> | null;
  constructor() {
    this.root = null;
  }
  left: PrintableNode | null = null;
  right: PrintableNode | null = null;
  parent: PrintableNode | null = null;
  value: any;

  // 提供模板方法给子类使用，子类如果创建的node不同，重写该方法
  protected createNode(value: T): TreeNode<T> {
    return new TreeNode(value);
  }

  insert(value: T) {
    // const node = new TreeNode<T>(value);
    const node = this.createNode(value);
    if (this.root === null) {
      this.root = node;
    } else {
      this.insertNode(this.root, node);
    }

    // 检查树是否平衡
    this.checkBalance(node);
  }

  protected checkBalance(node: TreeNode<T>) {}

  private insertNode(root: TreeNode<T>, newNode: TreeNode<T>) {
    if (root.value > newNode.value) {
      if (root.left === null) {
        root.left = newNode;
        newNode.root = root;
      } else {
        this.insertNode(root.left, newNode);
      }
    } else {
      if (root.right === null) {
        root.right = newNode;
        newNode.root = root;
      } else {
        this.insertNode(root.right, newNode);
      }
    }
  }

  print() {
    btPrint(this.root);
  }

  PrintableNode() {}

  // 先序遍历
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root);
  }

  private preOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      console.log(node.value);
      this.preOrderTraverseNode(node.left);
      this.preOrderTraverseNode(node.right);
    }
  }

  inOrderTraverse() {
    this.inOrderTraveseNode(this.root);
  }

  // 中序遍历
  private inOrderTraveseNode(node: TreeNode<T> | null) {
    if (node) {
      this.inOrderTraveseNode(node.left);
      console.log(node.value);
      this.inOrderTraveseNode(node.right);
    }
  }

  // 后序遍历
  postOrderTraverse() {
    this.postOrderTraverseNode(this.root);
  }

  private postOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      this.postOrderTraverseNode(node.left);
      this.postOrderTraverseNode(node.right);
      console.log(node.value);
    }
  }

  // 层序遍历
  levelOrderTraver() {
    if (!this.root) return;
    const queue: TreeNode<T>[] = [];
    queue.push(this.root);

    while (queue.length) {
      const current = queue.shift()!;
      console.log(current.value);

      if (current.left) {
        queue.push(current.left);
      }

      if (current.right) {
        queue.push(current.right);
      }
    }
  }

  min(): T | null {
    if (this.root === null) return null;
    let current = this.root;
    while (current?.left) {
      current = current.left;
    }

    return current?.value;
  }

  max(): T | null {
    if (this.root === null) return null;
    let current = this.root;
    while (current.right) {
      current = current.right;
    }

    return current.value;
  }

  search(value: T): boolean {
    return !!this.searchNode(value);
  }

  private searchNode(value: T): TreeNode<T> | null {
    if (this.root === null) return null;

    let current: TreeNode<T> | null = this.root;
    let parent: TreeNode<T> | null = null;
    while (current) {
      if (current.value === value) {
        return current;
      }

      parent = current;

      if (current.value < value) {
        current = current.right!;
      }
      if (current.value > value) {
        current = current.left!;
      }

      if (current) current.root = parent;
    }

    return null;
  }

  remove(value: T): boolean {
    if (this.root === null) return false;
    let current: TreeNode<T> | null = this.root;
    let parent: TreeNode<T> | null = null;
    while (current !== null) {
      if (current.value === value) {
        break;
      }
      parent = current;
      if (current.value < value) {
        current = current.right;
      } else {
        current = current.left;
      }
    }

    // 循环结束后没查找到，直接返回false
    if (current?.value !== value) return false;

    if (current!.left === null || current!.right === null) {
      const child = current!.left || current!.right;
      if (current === this.root) {
        this.root = child;
      } else if (parent!.left === current) {
        parent!.left = child;
      } else {
        parent!.right = child;
      }
    } else {
      let temp = current.right!;
      while (temp.left !== null) {
        temp = temp.left;
      }
      this.remove(temp.value);
      current.value = temp.value;
    }

    this.checkBalance(current);
    return true;
  }
}

class Product {
  constructor(public name: string, public price: number) {}

  valueOf() {
    return this.price;
  }

  toString() {
    return this.name + " " + this.price;
  }
}

/* const bst = new SearchTree<number>();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(6);

bst.print();

bst.remove(11);
bst.print(); */

/* bst.levelOrderTraver();
console.log(bst.search(20));
console.log(bst.search(21)); */

export {};
